﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目:
//给出一个长度为 n 的单链表和一个值 x ，单链表的每一个值为 listi ，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，
//并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。
//例如：
//给出: 1→4→3→2→5→2 和 x = 3		返回: 1→2→2→4→3→5
//数据范围：n≤200  −100≤list[i]≤100
//进阶：时间复杂度 O(n)， 空间复杂度 O(1)

#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode
{
    int val;
    struct ListNode* next;
}ListNode;
struct ListNode* Creatnewnode(int x)
{
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newnode == NULL)
    {
        perror("fail malloc");
        return NULL;
    }
    newnode->val = x;
    newnode->next = NULL;

    return newnode;
}
struct ListNode* partition(struct ListNode* head, int x)
{
    // write code here
    if (head == NULL)
        return NULL;

    struct ListNode* tail = head;
    struct ListNode* phead = NULL;
    struct ListNode* pf = NULL;
    int flag = 1;
    while (tail)
    {
        if (tail->val < x)
        {
            if (flag)
            {
                phead = Creatnewnode(tail->val);
                pf = phead;
                tail = tail->next;
                flag = 0;
            }
            else
            {
                pf->next = Creatnewnode(tail->val);
                pf = pf->next;
                tail = tail->next;
            }
        }
        else
            tail = tail->next;
    }
    //小的插完了
    tail = head;
    while (tail)
    {
        if (tail->val >= x)
        {
            if (flag)
            {
                phead = Creatnewnode(tail->val);
                pf = phead;
                tail = tail->next;
                flag = 0;
            }
            else
            {
                pf->next = Creatnewnode(tail->val);
                pf = pf->next;
                tail = tail->next;
            }
        }
        else
            tail = tail->next;
    }
    return phead;
}
int main()
{

	return 0;
}